/**
 * 剑指 Offer 36. 二叉搜索树与双向链表
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 */
public class Solutions_Offer_36 {
    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);  // output: {1, 2, 3, 4, 5}

        Node result = treeToDoublyList(root);
        System.out.println(result);
    }

    // 头节点
    private static Node head = null;
    // 记录当前遍历节点的前一节点（中序遍历方式）
    private static Node pre = null;

    public static Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        dfs(root);
        // 头结点的前趋是尾结点
        head.left = pre;
        // 尾结点的后继是头结点
        pre.right = head;
        // 返回头结点
        return head;
    }

    // 中序遍历二叉搜索树，得到的元素是升序排列
    public static void dfs(Node root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (head == null) {
            head = root;
        }
        // 当前节点是前一节点的 right 节点
        // 当前节点的 left 节点是 pre 节点
        if (pre != null) {
            pre.right = root;
        }
        root.left = pre;
        pre = root;
        dfs(root.right);
    }
}


